class Solution {
public:
    string findLexSmallestString(string s, int a, int b) {
        int n = s.size();
        vector<bool> vie(n, false);
        string res = s;
        s = s + s;
        for (int i = 0; vie[i] == false; i = (i + b) % n) {
            vie[i] = true;
            for (int j = 0; j < 10; j++) {
                int maxk = b % 2 == 0 ? 0 : 9;
                for (int k = 0; k <= maxk; k++) {
                    string tmp = s.substr(i, n);
                    for (int x = 1; x < n; x += 2)
                        tmp[x] = '0' + (tmp[x] - '0' + a * j) % 10;
                    for (int x = 0; x < n; x += 2)
                        tmp[x] = '0' + (tmp[x] - '0' + a * k) % 10;
                    res = min(res, tmp);
                }
            }
        }


        return res;
    }
};